#include <qlib/tools/clipper_tools.h>

namespace qlib {

Clipper2Lib::Path64 polygon_to_path(Polygon::s_ptr polygon, double scaling) {
  scaling = 1e3;  //统一用三位精度
  bool reverse = polygon->signed_area() < 0;
  uint64_t num = polygon->points.size();
  Clipper2Lib::Path64 path;
  path.reserve(num);
  if (reverse) {
    for (int i = 0; i < num; i++) {
      auto p = polygon->points[num - 1 - i];
      path.push_back(Clipper2Lib::Point64(llround(scaling * p.x), llround(scaling * p.y)));
    }
  } else {
    for (int i = 0; i < num; i++) {
      auto p = polygon->points[i];
      path.push_back(Clipper2Lib::Point64(llround(scaling * p.x), llround(scaling * p.y)));
    }
  }
  return path;
}
Clipper2Lib::Paths64 polygons_to_paths(const PolygonPtrArray& polygon_array, double scaling) {
  scaling = 1e3;  //统一用三位精度
  uint64_t num = polygon_array.size();
  Clipper2Lib::Paths64 paths;
  paths.reserve(num);
  for (auto&& p : polygon_array)
    paths.push_back(polygon_to_path(p, scaling));
  return paths;
}

Polygon::s_ptr path_to_polygon(const Clipper2Lib::Path64& path, double scaling) {
  scaling = 1e3;  //统一用三位精度
  const double invscaling = 1 / scaling;
  uint64_t num = path.size();
  auto polygon = Polygon::create();
  polygon->points.resize(num);

  for (int i = 0; i < num; i++) {
    polygon->points[i].x = invscaling * path[i].x;
    polygon->points[i].y = invscaling * path[i].y;
  }
  return polygon;
}

struct SortPath {
  int path_id;
  int min_point_id;
  Clipper2Lib::Point64 min_point;
};
bool point_less(const Clipper2Lib::Point64& p1, const Clipper2Lib::Point64& p2) {
  return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
}
bool path_less(const SortPath& p1, const SortPath& p2) {
  return point_less(p1.min_point, p2.min_point);
}
void link_holes(Clipper2Lib::PolyPath64* node, Clipper2Lib::Path64& contour, std::set<Clipper2Lib::PolyTree64*>& trees) {
  std::vector<SortPath> holes;
  holes.reserve(node->Count());

  contour = node->Polygon();
  uint64_t count = contour.size();

  //求内部洞边界的最小坐标值
  for (int i = 0; i < node->Count(); i++) {
    count += node->Child(i)->Polygon().size() + 3;
    SortPath sp;
    sp.path_id = i;
    sp.min_point_id = 0;
    sp.min_point = node->Child(i)->Polygon()[0];
    for (int j = 0; j < node->Child(i)->Polygon().size(); j++) {
      if (point_less(node->Child(i)->Polygon()[j], node->Child(i)->Polygon()[sp.min_point_id])) {
        sp.min_point_id = j;
        sp.min_point = node->Child(i)->Polygon()[j];
      }
    }
    holes.push_back(sp);

    for (auto j = 0; j < node->Child(i)->Count(); j++) {
      auto temp = node->Child(i)->Child(j);
      if (!(temp->IsHole())) {
        trees.insert(temp);
      }
    }
  }
  contour.reserve(count);

  //按照最小坐标值对洞边界排序
  std::sort(holes.begin(), holes.end(), path_less);
  //gds_utils::sort(holes, path_less);

  //将洞边界与外边界连接，形成一个多边形
  for (uint64_t i = 0; i < holes.size(); i++) {
    // holes are guaranteed to be oriented opposite to their parent
    int min_point_id = holes[i].min_point_id;
    Clipper2Lib::Point64 hole_min = holes[i].min_point;
    const Clipper2Lib::Path64::iterator p_end = contour.end();
    Clipper2Lib::Path64::iterator p_closest = contour.end();
    Clipper2Lib::Path64::iterator p_prev = contour.end() - 1;
    Clipper2Lib::Path64::iterator p_next = contour.begin();
    int64_t xnew = 0;
    for (; p_next != p_end; p_prev = p_next++) {
      if ((p_next->y <= hole_min.y && hole_min.y < p_prev->y) || (p_prev->y < hole_min.y && hole_min.y <= p_next->y)) {
        int64_t x = p_next->x + ((p_prev->x - p_next->x) * (hole_min.y - p_next->y)) / (p_prev->y - p_next->y);
        if ((x > xnew || p_closest == p_end) && x <= hole_min.x) {
          xnew = x;
          p_closest = p_next;
        }
      } else if ((p_next->y == hole_min.y && p_prev->y == hole_min.y) &&
                 ((p_next->x <= hole_min.x && hole_min.x <= p_prev->x) || (p_prev->x <= hole_min.x && hole_min.x <= p_next->x))) {
        xnew = hole_min.x;
        p_closest = p_next;
        break;
      }
    }

    if (p_closest == p_end) {
      fprintf(stderr, "[GDS] Unable to link hole in boolean operation.\n");
    } else {
      Clipper2Lib::Point64 p_new(xnew, hole_min.y);
      if (p_new.x != p_closest->x || p_new.y != p_closest->y)
        p_closest = contour.insert(p_closest, p_new);
      p_closest = contour.insert(p_closest, node->Child(holes[i].path_id)->Polygon().begin(),
                                 node->Child(holes[i].path_id)->Polygon().begin() + holes[i].min_point_id + 1);
      p_closest = contour.insert(p_closest, node->Child(holes[i].path_id)->Polygon().begin() + holes[i].min_point_id,
                                 node->Child(holes[i].path_id)->Polygon().end());
      contour.insert(p_closest, p_new);
    }
  }
  holes.clear();
}
void tree_to_polygons(const Clipper2Lib::PolyTree64& tree, double scaling, PolygonPtrArray& polygon_array, std::vector<bool>& polygon_hole) {
  auto node = tree.begin();
  std::set<Clipper2Lib::PolyTree64*> trees;
  while (node != tree.end() || !trees.empty()) {
    if (node != tree.end()) {
      bool is_hole = false;
      if (!(*node)->IsHole()) {
        //节点下面还有子节点就是有洞的情况
        if ((*node)->Count() > 0) {
          Clipper2Lib::Path64 path;
          link_holes((*node).get(), path, trees);
          polygon_array.push_back(path_to_polygon(path, scaling));
          is_hole = true;
          polygon_hole.push_back(is_hole);

        } else {
          polygon_array.push_back(path_to_polygon((*node)->Polygon(), scaling));
          polygon_hole.push_back(is_hole);
        }
      }
      node++;
    } else {
      bool is_hole = false;
      auto temp_node = trees.begin();
      if (!(*temp_node)->IsHole()) {
        //节点下面还有子节点就是有洞的情况
        if ((*temp_node)->Count() > 0) {
          Clipper2Lib::Path64 path;
          link_holes((*temp_node), path, trees);
          polygon_array.push_back(path_to_polygon(path, scaling));
          is_hole = true;
          polygon_hole.push_back(is_hole);

        } else {
          polygon_array.push_back(path_to_polygon((*temp_node)->Polygon(), scaling));
          polygon_hole.push_back(is_hole);
        }
      }

      trees.erase(*temp_node);
    }
  }
}

static void bounding_box(Clipper2Lib::Path64& points, int64_t* bb) {
  bb[0] = points[0].x;
  bb[1] = points[0].x;
  bb[2] = points[0].y;
  bb[3] = points[0].y;
  for (Clipper2Lib::Path64::iterator it = points.begin(); it != points.end(); it++) {
    if (it->x < bb[0])
      bb[0] = it->x;
    if (it->x > bb[1])
      bb[1] = it->x;
    if (it->y < bb[2])
      bb[2] = it->y;
    if (it->y > bb[3])
      bb[3] = it->y;
  }
}

void ClipperTool::boolean(PolygonPtrArray op1, PolygonPtrArray op2, Operation operation, double scaling, PolygonPtrArray& result) {
  //布尔运算统一三位精度计算
  scaling = 1e3;
  Clipper2Lib::ClipType ct_operation = Clipper2Lib::ClipType::Union;
  switch (operation) {
    case Operation::Or:
      ct_operation = Clipper2Lib::ClipType::Union;
      break;
    case Operation::And:
      ct_operation = Clipper2Lib::ClipType::Intersection;
      break;
    case Operation::Xor:
      ct_operation = Clipper2Lib::ClipType::Xor;
      break;
    case Operation::Not:
      ct_operation = Clipper2Lib::ClipType::Difference;
  }

  Clipper2Lib::Paths64 paths1 = polygons_to_paths(op1, scaling);
  Clipper2Lib::Paths64 paths2 = polygons_to_paths(op2, scaling);

  Clipper2Lib::Clipper64 clpr;
  clpr.AddSubject(paths1);
  clpr.AddClip(paths2);

  Clipper2Lib::PolyTree64 solution;
  Clipper2Lib::FillRule fr = Clipper2Lib::FillRule::NonZero;
  clpr.Execute(ct_operation, fr, solution);

  std::vector<bool> polygon_hole;
  tree_to_polygons(solution, scaling, result, polygon_hole);
}

void ClipperTool::slice(Polygon::s_ptr polygon, const std::vector<double>& positions, bool x_axis, double scaling,
                        std::vector<PolygonPtrArray>& result) {
  scaling = 1e3;
  result.resize(positions.size() + 1);
  Clipper2Lib::Paths64 subj;
  subj.push_back(polygon_to_path(polygon, scaling));

  int64_t bb[4];
  bounding_box(subj[0], bb);

  Clipper2Lib::Paths64 clip(1, Clipper2Lib::Path64(4));
  clip[0][0].x = clip[0][3].x = bb[0];
  clip[0][1].x = clip[0][2].x = bb[1];
  clip[0][0].y = clip[0][1].y = bb[2];
  clip[0][2].y = clip[0][3].y = bb[3];

  int64_t pos = x_axis ? bb[0] : bb[2];
  for (uint64_t i = 0; i <= positions.size(); i++) {
    if (x_axis) {
      clip[0][0].x = clip[0][3].x = pos;
      pos = i < positions.size() ? llround(scaling * positions[i]) : bb[1];
      clip[0][1].x = clip[0][2].x = pos;
    } else {
      clip[0][0].y = clip[0][1].y = pos;
      pos = i < positions.size() ? llround(scaling * positions[i]) : bb[3];
      clip[0][2].y = clip[0][3].y = pos;
    }

    // NOTE: ioStrictlySimple seems to hang on complex layouts
    // Clipper2Lib::Clipper clpr(Clipper2Lib::ioStrictlySimple);
    Clipper2Lib::Clipper64 clpr;
    clpr.AddSubject(subj);
    clpr.AddClip(clip);

    Clipper2Lib::PolyTree64 solution;
    Clipper2Lib::FillRule fr = Clipper2Lib::FillRule::NonZero;
    clpr.Execute(Clipper2Lib::ClipType::Intersection, fr, solution);

    std::vector<bool> polygon_hole;
    tree_to_polygons(solution, scaling, result[i], polygon_hole);
  }
}

void ClipperTool::offsetProcess(const PolygonPtrArray& polygons, double distance, OffsetJoin join, double tolerance, double scaling, bool use_union,
                                PolygonPtrArray& result) {
  SPDLOG_INFO("[ClipperTool] offset --begin");
  // 器件剔除
  // 多线程处理
  std::mutex vectorMutex;
  const size_t num_threads = std::min<size_t>(std::thread::hardware_concurrency(), polygons.size());
  std::vector<std::thread> threads;
  std::atomic<int> threads_remaining(num_threads);
  size_t size = polygons.size();
  size_t chunk_size = size / num_threads;
  size_t remainder = size % num_threads;
  size_t start = 0;
  for (size_t i = 0; i < num_threads; ++i) {
    size_t end = start + chunk_size + (i < remainder ? 1 : 0);
    // threads.emplace_back(&ClipperTool::remove_process_range, this, entvec.begin() + start, entvec.begin() + end, avoid_kd_arr, std::ref(vectorMutex));
    PolygonPtrArray poly;
    for (auto it = polygons.begin() + start; it != polygons.begin() + end; ++it) {
      poly.push_back(*it);
    }
    threads.emplace_back(&ClipperTool::offsetProcessRange, poly, distance, join, tolerance, scaling, use_union, std::ref(vectorMutex),
                         std::ref(threads_remaining), std::ref(result));
    start = end;
  }
  std::thread monitor([&]() {
    while (threads_remaining > 0) {
      std::cout << "[ClipperTool] remaining_threads --: " << threads_remaining.load() << std::endl;
      std::this_thread::sleep_for(std::chrono::milliseconds(2000));
    }
  });
  // 等待所有线程完成
  for (auto& thread : threads) {
    thread.join();
  }
  monitor.join();
  SPDLOG_INFO("[ClipperTool] monitor -- end");
}

void ClipperTool::offsetProcessRange(PolygonPtrArray poly, double distance, OffsetJoin join, double tolerance, double scaling, bool use_union,
                                     std::mutex& vectorMutex, std::atomic<int>& threads_remaining, PolygonPtrArray& result) {
  Clipper2Lib::JoinType jt_join = Clipper2Lib::JoinType::Square;
  Clipper2Lib::ClipperOffset clprof;
  switch (join) {
    case OffsetJoin::Bevel:
      jt_join = Clipper2Lib::JoinType::Square;
      break;
    case OffsetJoin::Miter:
      jt_join = Clipper2Lib::JoinType::Miter;
      clprof.MiterLimit(tolerance);
      break;
    case OffsetJoin::Round:
      jt_join = Clipper2Lib::JoinType::Round;
      clprof.ArcTolerance(distance * scaling * (1.0 - cos(M_PI / tolerance)));
  }

  Clipper2Lib::Paths64 original_polys = polygons_to_paths(poly, scaling);
  if (use_union) {
    Clipper2Lib::Clipper64 clpr;
    clpr.AddSubject(original_polys);
    Clipper2Lib::PolyTree64 joined_tree;

    Clipper2Lib::FillRule fr = Clipper2Lib::FillRule::NonZero;
    clpr.Execute(Clipper2Lib::ClipType::Union, fr, joined_tree);

    Clipper2Lib::Paths64 joined_polys;
    joined_polys = Clipper2Lib::PolyTreeToPaths64(joined_tree);

    clprof.AddPaths(joined_polys, jt_join, Clipper2Lib::EndType::Polygon);
  } else {
    clprof.AddPaths(original_polys, jt_join, Clipper2Lib::EndType::Polygon);
  }

  Clipper2Lib::PolyTree64 solution;
  clprof.Execute(distance * scaling, solution);

  std::vector<bool> polygon_hole;
  PolygonPtrArray res;
  tree_to_polygons(solution, scaling, res, polygon_hole);
  if (res.size()) {
    std::lock_guard<std::mutex> guard(vectorMutex);
    result.insert(result.end(), res.begin(), res.end());
  }
  threads_remaining--;
}

void ClipperTool::offset(const PolygonPtrArray& polygons, double distance, OffsetJoin join, double tolerance, double scaling, bool use_union,
                         PolygonPtrArray& result) {
  Clipper2Lib::JoinType jt_join = Clipper2Lib::JoinType::Square;
  Clipper2Lib::ClipperOffset clprof;
  switch (join) {
    case OffsetJoin::Bevel:
      jt_join = Clipper2Lib::JoinType::Square;
      break;
    case OffsetJoin::Miter:
      jt_join = Clipper2Lib::JoinType::Miter;
      clprof.MiterLimit(tolerance);
      break;
    case OffsetJoin::Round:
      jt_join = Clipper2Lib::JoinType::Round;
      clprof.ArcTolerance(distance * scaling * (1.0 - cos(M_PI / tolerance)));
  }

  Clipper2Lib::Paths64 original_polys = polygons_to_paths(polygons, scaling);
  if (use_union) {
    Clipper2Lib::Clipper64 clpr;
    clpr.AddSubject(original_polys);
    Clipper2Lib::PolyTree64 joined_tree;

    Clipper2Lib::FillRule fr = Clipper2Lib::FillRule::NonZero;
    clpr.Execute(Clipper2Lib::ClipType::Union, fr, joined_tree);

    Clipper2Lib::Paths64 joined_polys;
    joined_polys = Clipper2Lib::PolyTreeToPaths64(joined_tree);

    clprof.AddPaths(joined_polys, jt_join, Clipper2Lib::EndType::Polygon);
  } else {
    clprof.AddPaths(original_polys, jt_join, Clipper2Lib::EndType::Polygon);
  }

  Clipper2Lib::PolyTree64 solution;
  clprof.Execute(distance * scaling, solution);

  std::vector<bool> polygon_hole;
  tree_to_polygons(solution, scaling, result, polygon_hole);
}

std::shared_ptr<double> getSlope(Vec2d p1, Vec2d p2) {
  std::shared_ptr<double> reslut = nullptr;
  double x1 = p1.x;
  double x2 = p2.x;
  double y1 = p1.y;
  double y2 = p2.y;
  double delta_x = x2 - x1;
  if (delta_x != 0)
    reslut = std::make_shared<double>((y2 - y1) / delta_x);

  return reslut;
};

std::vector<std::shared_ptr<double>> slopeAndIntercept(Vec2d p1, Vec2d p2, std::shared_ptr<double> s) {
  double x1 = p1.x;
  double x2 = p2.x;
  double y1 = p1.y;
  double y2 = p2.y;
  std::shared_ptr<double> slope = nullptr;
  if (s != nullptr) {
    slope = std::make_shared<double>(*s);
  }

  std::shared_ptr<double> intercept = nullptr;
  if (slope != nullptr)
    intercept = std::make_shared<double>(y1 - (*slope) * x1);
  if (slope == nullptr) {
    intercept = std::make_shared<double>(x1);
  }
  std::vector<std::shared_ptr<double>> result;
  result.push_back(slope);
  result.push_back(intercept);
  return result;
}

Vec2d calculateIntersectionPoint(std::vector<std::shared_ptr<double>> line_a, std::vector<std::shared_ptr<double>> line_b) {
  std::shared_ptr<double> a = line_a[0];
  std::shared_ptr<double> b = line_b[0];
  std::shared_ptr<double> c = line_a[1];
  std::shared_ptr<double> d = line_b[1];
  double px;
  double py;
  if (a == nullptr) {
    px = *c;
    py = *b * px + *d;
  } else if (b == nullptr) {
    px = *d;
    py = *a * px + *c;
  } else {
    px = (*d - *c) / (*a - *b);
    py = *a * px + *c;
  }

  return Vec2d(px, py);
};

bool lineIntersectSeg(Vec2d p, Vec2d q, Vec2d A, Vec2d B, Vec2d& inter_point) {
  std::shared_ptr<double> slope_1 = getSlope(p, q);
  std::shared_ptr<double> slope_2 = getSlope(A, B);
  std::vector<std::shared_ptr<double>> line_c_last = slopeAndIntercept(p, q, slope_1);
  std::vector<std::shared_ptr<double>> line_last_d = slopeAndIntercept(A, B, slope_2);

  // 平行线没有交点
  if (!line_c_last[0] && !line_last_d[0])
    return false;
  if (line_c_last[0] && line_last_d[0]) {
    if (abs(*line_c_last[0] - *line_last_d[0]) < 10e-7)
      return false;
  }

  inter_point = calculateIntersectionPoint(line_c_last, line_last_d);
  {
    double dis_1 = (p - inter_point).length();
    double dis_2 = (q - inter_point).length();
    double dis = (p - q).length();

    if (abs(dis - dis_1 - dis_2) > 10e-5)
      return false;
  }

  {
    double dis_1 = (A - inter_point).length();
    double dis_2 = (B - inter_point).length();
    double dis = (A - B).length();

    if (abs(dis - dis_1 - dis_2) > 10e-5)
      return false;
  }

  return true;
}

void ClipperTool::slice(Path::s_ptr path, double x, double y, bool x_axis, PathPtrArray& result) {
  std::vector<std::vector<Vec2d>> split_lines;

  std::vector<Vec2d> temp;
  for (int i = 0; i < path->spine.points.size() - 1; i++) {
    auto p = path->spine.points[i];
    auto q = path->spine.points[i + 1];

    bool is_inter = false;
    Vec2d inter_point;

    bool is_horizontal_slicing = !x_axis;

    if (is_horizontal_slicing) {
      if (lineIntersectSeg(Vec2d(p.x, p.y), Vec2d(q.x, q.y), Vec2d(-1e7, y), Vec2d(1e7, y), inter_point))
        is_inter = true;
    } else {
      if (lineIntersectSeg(Vec2d(p.x, p.y), Vec2d(q.x, q.y), Vec2d(x, -1e7), Vec2d(x, 1e7), inter_point))
        is_inter = true;
    }
    if (is_inter == true) {
      if ((p - Vec2d(inter_point.x, inter_point.y)).length() < 10e-5)
        is_inter = false;
    }
    if (is_inter) {
      temp.push_back(p);
      temp.push_back(Vec2d(inter_point.x, inter_point.y));
      split_lines.push_back(temp);
      temp.clear();
      if ((q - Vec2d(inter_point.x, inter_point.y)).length() < 10e-5) {

      } else {
        temp.push_back(Vec2d(inter_point.x, inter_point.y));
      }
    } else {
      temp.push_back(p);
    }
  }
  temp.push_back(path->spine.points[path->spine.points.size() - 1]);
  split_lines.push_back(temp);

  for (auto i : split_lines) {
    auto res_path = path->copy();
    res_path->spine.points = i;
    result.push_back(res_path);
  }
}

void ClipperTool::pathIntersectWithRect(Path::s_ptr _path, Rectangle::s_ptr _rect, PathPtrArray& _result) {
  //   Clipper2Lib::Path64 line = {Clipper2Lib::Point64(0, 200), Clipper2Lib::Point64(50, -50), Clipper2Lib::Point64(100, 200)};

  //   Clipper2Lib::Path64 polygon = {Clipper2Lib::Point64(0, 0), Clipper2Lib::Point64(0, 100), Clipper2Lib::Point64(100, 100),
  //                                  Clipper2Lib::Point64(100, 0)};
  Clipper2Lib::Path64 line;
  Clipper2Lib::Path64 polygon;
  double scaling = 1e3;  //统一用三位精度
  double invscaling = 1 / scaling;
  uint64_t path_points_num = _path->spine.points.size();
  for (int i = 0; i < path_points_num; i++) {
    auto p = _path->spine.points[i];
    line.push_back(Clipper2Lib::Point64(llround(scaling * p.x), llround(scaling * p.y)));
  }
  Polygon::s_ptr _poly = _rect->to_polygon();
  uint64_t poly_points_num = _poly->points.size();
  for (int i = 0; i < poly_points_num; i++) {
    auto p = _poly->points[i];
    polygon.push_back(Clipper2Lib::Point64(llround(scaling * p.x), llround(scaling * p.y)));
  }

  Clipper2Lib::Paths64 paths;
  Clipper2Lib::Paths64 polys;
  paths.push_back(line);
  polys.push_back(polygon);
  // 3. 创建Clipper对象
  Clipper2Lib::Clipper64 clipper;

  // 4. 添加线和多边形
  // 注意：线需要作为开放路径添加
  clipper.AddOpenSubject(paths);
  clipper.AddClip(polys);

  // 5. 执行交集操作
  Clipper2Lib::Paths64 solution;   //close path
  Clipper2Lib::Paths64 solution2;  //open path
  clipper.Execute(Clipper2Lib::ClipType::Intersection, Clipper2Lib::FillRule::NonZero, solution, solution2);

  // 6. 输出结果
  std::cout << "Intersection results:" << std::endl;
  for (const auto& res_path : solution2) {
    qlib::Path::s_ptr path_t = qlib::Path::create();
    path_t->layer = _path->layer;
    path_t->width = _path->width;
    path_t->center_width = _path->center_width;
    path_t->radius = _path->radius;
    path_t->update();

    for (const auto& pt : res_path) {
      std::cout << "(" << pt.x << ", " << pt.y << ") ";
      path_t->spine.points.push_back(qlib::Vec2d(pt.x * invscaling, pt.y * invscaling));
    }
    _result.push_back(path_t);

    std::cout << std::endl;
  }
}
}  // namespace qlib